package com.heima.datastructure.priorityqueue;

import com.heima.datastructure.queue.Queue;

import java.util.Iterator;
import java.util.PriorityQueue;

/**
 * 基于有序数组实现优先级队列
 *
 * @param <E> 实现优先级接口的类
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/3 10:12
 */
public class PriorityQueue2<E extends Priority> implements Queue<E>, Iterable<Integer> { // 这里迭代器的泛型指定为Integer是为了迭代遍历时只遍历类的实例的优先级
    // 1、有序数组里面存的元素是实现了优先级接口的类实例
    // 2、有序数组，所以数组中的排序是按照优先级来的，从数组末尾删除性能高，所以数组头到尾对应着优先级低到高
    // 3、poll方法就只用移除队尾元素，peek方法获取数组尾元素
    // 4、offer方法就需要插入元素到有序数组的合理位置去，也就是插入排序

    // arr中存的是一个个地址，引用的分别是Priority的实现类E的实例
    // 假设这里的E是Entry
    // 就相当于执行Priority p1 = new Entry();
    // 就相当于执行Priority p2 = new Entry();
    // 就相当于执行Priority p3 = new Entry();
    // ...
    // 把p1，p2，p3...存到这个数组中去，
    // 当从arr中取出p1时，只能调用Priority有的方法，又p1引用的Entry的实例，而且Entry是重写或实现了Priority中的方法的，所以会调用Priority中的方法就会被覆盖，实则调用的子类或实现类的该方法
    // 取出来的p1是Priority类型，但是当poll时需要返回的是Entry类型，由于存的时候是将Entry强制转化为Priority存进去的，所以此时接口到实现类的强制类型转化是可以转化的
    private Priority[] arr; // 有序数组，一来，优先级队列只关心优先级，二来，子类转父类属于多态，肯定可以转换的（包括接口和实现），父类转子类得有条件：父类对象引用的对象是这个子类的实例，才能父类转子类，才有意义。那么添加的时候让父类或者接口对象指向E对象的实例，从而取出来的时候可以达成父类转子类的有意义效果
    private int size; // 当前队列的大小，同时指向数组尾元素的后一个元素，默认初始化尾0

    /**
     * 用构造器初始化
     *
     * @param capacity
     */
    @SuppressWarnings("all")
    public PriorityQueue2(int capacity) {
        arr = new Priority[capacity];
    }

    /**
     * 入队 O(n)
     *
     * @param value 待插入值
     * @return 入队成功返回true
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        insert(value);
        return true;
    }

    /**
     * 出队并删除 O(1)
     *
     * @return 出队的元素
     */
    @SuppressWarnings("all")
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Priority value = arr[--size];
        arr[size] = null;
        return (E) value; // 存的时候多态，取的时候才可以强制类型转换
    }

    /**
     * 获取优先级最高的元素
     *
     * @return 优先级最高的元素
     */
    @SuppressWarnings("all")
    @Override
    public E peek() {
        return (E) arr[size - 1];
    }

    /**
     * 判断是否为空
     *
     * @return 空返回true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * 迭代器，这里因为数组是有序的，所以迭代遍历的结果是优先级由低到高
     *
     * @return 迭代器
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;

            @Override
            public boolean hasNext() {
                return index != size;
            }

            @SuppressWarnings("all")
            @Override
            public Integer next() {
                Priority value = arr[index];
                index++;
                return value.priority(); // 多态，调用的是重写过后的方法
            }
        };
    }

    /**
     * 插入元素到有序数组的合理位置中，插入排序
     *
     * @param value 待插入元素
     */
    private void insert(E value) {
        int i = size - 1;
        while (i >= 0 && arr[i].priority() > value.priority()){
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = value; // 多态
        size++;
    }

    /**
     * 扩容
     * @param capacity 容量
     */
    public void expansion(int capacity) {
        if (capacity <= arr.length) {
            throw new IllegalArgumentException("参数 <" + capacity + "> 不能比" + arr.length + "小");
        }
        Priority[] array = new Priority[capacity];
        System.arraycopy(arr, 0, array, 0, size);
        arr = array;
    }
}
